package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 二叉树的锯齿形层序便利
 * https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
 *
 * @time 2024/1/8
 */
public class ZigzagLevelOrder {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        search(root, 0);
        List<List<Integer>> ans = map.entrySet().stream()
                .sorted(new Comparator<Map.Entry<Integer, List<Integer>>>() {
                    @Override
                    public int compare(Map.Entry<Integer, List<Integer>> o1, Map.Entry<Integer, List<Integer>> o2) {
                        return o1.getKey().compareTo(o2.getKey());
                    }
                })
                .map(e -> {
                    if (e.getKey() % 2 == 1) {
                        Collections.reverse(e.getValue());
                    }
                    return e.getValue();
                })
                .collect(Collectors.toList());
        return ans;
    }

    private Map<Integer, List<Integer>> map = new HashMap<>();

    private void search(TreeNode root, int step) {
        if (null == root) {
            return;
        }
        List<Integer> list = null;
        if (map.containsKey(step)) {
            list = map.get(step);
        } else {
            list = new ArrayList<>();
            map.put(step, list);
        }
        list.add(root.val);
        search(root.left, step + 1);
        search(root.right, step + 1);
    }
}
